#!/usr/bin/env python3

def quick_sort(array, start=0, end=None):
    if end is None:
        end = len(array)
    if end - start <= 1:
        return
    partition_index = partition(array, start, end)
    #print("partition_index is %d, start is %d, end is %d" % (partition_index, start, end))
    quick_sort(array, start, partition_index)
    quick_sort(array, partition_index + 1, end)

def partition(array, start, end):
    current_pivot_index = end - 1
    pivot_value = array[current_pivot_index]
    for index in range(start, end - 1):
        if (array[index] > pivot_value and index < current_pivot_index) or (array[index] < pivot_value and index > current_pivot_index):
            array[index], array[current_pivot_index] = array[current_pivot_index], array[index]
            current_pivot_index = index
    return current_pivot_index


def test_quick_sort():
    array = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    quick_sort(array)
    assert 1 == array[0]
    assert 4 == array[3]
    assert 9 == array[8]
    array = [9, 8, 7, 6, 5, 4, 3, 2, 1]
    quick_sort(array)
    assert 1 == array[0]
    assert 4 == array[3]
    assert 9 == array[8]
